package com.sheng.leetcode.year2023.month07.day13;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2023/07/13
 * <p>
 * 931. 下降路径最小和<p>
 * <p>
 * 给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。<p>
 * 下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。<p>
 * 在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。<p>
 * 具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]<p>
 * 输出：13<p>
 * 解释：如图所示，为和最小的两条下降路径<p>
 * <p>
 * 示例 2：<p>
 * 输入：matrix = [[-19,57],[-40,-5]]<p>
 * 输出：-59<p>
 * 解释：如图所示，为和最小的下降路径<p>
 * <p>
 * 提示：<p>
 * n == matrix.length == matrix[i].length<p>
 * 1 <= n <= 100<p>
 * -100 <= matrix[i][j] <= 100<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/minimum-falling-path-sum">931. 下降路径最小和</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode0931 {

    @Test
    public void test01() {
//        int[][] matrix = {{2, 1, 3}, {6, 5, 4}, {7, 8, 9}};
        int[][] matrix = {{-19, 57}, {-40, -5}};
        System.out.println(new Solution().minFallingPathSum(matrix));
    }
}

class Solution {

    int min = Integer.MAX_VALUE;

    int n;

    int[][] nums;

    public int minFallingPathSum(int[][] matrix) {
        n = matrix.length;
//        nums = matrix;
//        for (int i = 0; i < n; i++) {
//            dfs(i, matrix[0][i], 0);
//        }
//        return min;
        int[][] ints = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (i == n - 1) {
                    ints[i][j] = matrix[i][j];
                } else {
                    // 计算 matrix[i][j] 和下面三个数值的和的最小值
                    int min = ints[i + 1][j];
                    if (j > 0) {
                        min = Math.min(ints[i + 1][j - 1], min);
                    }
                    if (j < n - 1) {
                        min = Math.min(ints[i + 1][j + 1], min);
                    }
                    ints[i][j] = min + matrix[i][j];
                }
            }
        }
        int[] nums = ints[0];
        Arrays.sort(nums);
        return nums[0];
    }

    public void dfs(int index, int sum, int level) {
        if (level < n - 1) {
            // 继续向下
            // 左下方是否满足
            if (index - 1 >= 0) {
                dfs(index - 1, sum + nums[level + 1][index - 1], level + 1);
            }
            // 正下方
            dfs(index, sum + nums[level + 1][index], level + 1);
            // 右下方
            if (index + 1 <= n - 1) {
                dfs(index + 1, sum + nums[level + 1][index + 1], level + 1);
            }
        } else {
            min = Math.min(min, sum);
        }
    }
}

